package arithmetic.d_linklist;

import static utils.ListNodeUtils.createLinkSize;
import static utils.ListNodeUtils.printLink;

import utils.ListNodeUtils.ListNode;

/**
 * @author jiangfeng 2019/7/20 09:38
 * 翻转列表
 *
 *
 * 反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。
 *
 * 说明:
 * 1 ≤ m ≤ n ≤ 链表长度。
 *
 * 示例:
 *
 * 输入: 1->2->3->4->5->NULL, m = 2, n = 4
 * 输出: 1->4->3->2->5->NULL
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/reverse-linked-list-ii
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class ReserveLink {


    public static void main(String[] args) {
        ReserveLink reserveLink = new ReserveLink();
        ListNode test = createLinkSize(10);
        printLink(reserveLink.reverseBetween(test,1,10));
        printLink(reserveLink.reverseBetween(test,3,10));
        printLink(reserveLink.reverseBetween(test,3,8));
        printLink(reserveLink.reverseBetween(test,1,8));
        //printLink(reserveLink.reverseLink(test));
        printLink(reserveLink.reverseLink2(test));
    }

    // 考虑三种特殊情况 1.m=n 2.m是首， 3.n是尾
    public ListNode reverseBetween(ListNode head, int m, int n) {
        if (m == n) return head;
        ListNode newHead = null, preNodeM = null, nodeM = null,lastNode = null,thisNode=null;
        int i = 1;
        while (head != null) {
            thisNode = new ListNode(head.val);
            if (i == 1) {
                newHead = thisNode;
            }
            if (i < m - 1 || i > n+1) {
                if (lastNode != null) {
                    lastNode.next = thisNode;
                }
            } else if (i == m - 1) {
                preNodeM = thisNode;
                if (lastNode != null) {
                    lastNode.next = thisNode;
                }
            } else if (i == m) {
                nodeM = thisNode;
            } else if (m < i && i < n) {
                thisNode.next = lastNode;
            } else if (i == n) {
                if (m != 1) { // m是第一个的话，就没有preNodeM了
                    preNodeM.next = thisNode;
                } else {
                    newHead = thisNode;
                }
                if (head.next == null) {
                    nodeM.next = null; //n 是最后一个
                }
                thisNode.next = lastNode;
            } else if (i == n + 1) {
                nodeM.next = thisNode;
            }
            i++;
            lastNode = thisNode;
            head = head.next;
        }

        return newHead;
    }




    /**
     * 翻转链表
     * @param listNode
     * @return
     */
    public ListNode reverseLink(ListNode listNode){
        ListNode current=listNode,pre=null;
        while (current != null) {
            ListNode temp = current.next;
            current.next = pre;
            pre = current;
            current = temp;
        }
        return pre;
    }

    /**
     * 翻转链表2 递归法
     * @param listNode
     * @return
     */
    public ListNode reverseLink2(ListNode listNode) {
        if (listNode == null || listNode.next == null) {
            return listNode;
        }
        ListNode p = reverseLink2(listNode.next);
        listNode.next.next = listNode;
        listNode.next = null;
        return p;
    }

}
